\documentclass[10pt]{article}
\usepackage{amsmath}
\usepackage{graphicx}

\newcommand{\problem}[1]{\noindent{\sc Problem #1.}}
\newcommand{\solution}{\noindent{\sc Solution.}}
\newcommand{\complexity}{\noindent{\sc Complexity. }}
\newcommand{\answer}{\noindent{\sc Answer. }}
\newcommand{\given}{\,|\,}

\setlength{\parskip}{1ex plus 0.5ex minus 0.2ex}

\begin{document}

\problem{342}
The totient of a square is a cube.

Let $\varphi$ denote Euler's totient function. 

Consider the number 50. $50^2 = 2500 = 2^2 \times 5^4$, so $\varphi(2500) = (1 \times 2) \times (4 \times 5^3) = 2^3 \times 5^3$. So 2500 is a square and $\varphi(2500)$ is a cube.

Find the sum of all numbers $n$, $1 < n < 10^{10}$ such that $\varphi(n^2)$ is a cube.

\solution

Perform a prime factorization of $n$:
\[
n = p_1^{k_1} \cdots p_M^{k_M}
\]
It follows that
\[
\varphi(n^2) = (p_1-1) p_1^{2k_1-1} \cdots (p_M-1) p_M^{2 k_M-1} 
\]
%Then perform a prime factorization on $\varphi(n^2)$, which yields
%\[
%\varphi(n^2) = p_1^{l_1} \cdots p_m^{l_m} 
%\]
Examine these equations backwards from the last term to the first term. For the last term $p_M$, we must have $(2k_M-1)$ is divisible by 3, because there are no other terms $(p_i-1)$ that contains the prime factor $p_M$. Therefore $k_M \ge 2$. It follows that $p_M \le \sqrt{n}$, which gives an upper bound of the largest prime factor that satisfies this problem.

To simplify notation, given $n$, let $\varphi_m$ denote the partial product of the terms in $\varphi(n^2)$ starting from the $m$th term, i.e.
\[
\varphi_m = (p_m-1) p_m^{2k_m-1} \cdots (p_M-1) p_M^{2 k_M-1}
\]
where $1 \le m \le M$. It is easy to see that $\varphi_m = (p_m-1)p_m^{2k_m-1} \varphi_{m+1}$ and $\varphi(n^2)=\varphi_1$. Also, write the prime factorization of $\varphi_m$ as
\[
\varphi_m = \prod_{i=1}^M p_i^{l_{m,i}}
\]
and define the vector $l_m$ to be the \emph{power representation} of $\varphi_m$.

Now consider a term in the middle, $(p_m-1)p_m^{2k_m-1}$. Suppose the partial product $\varphi_{m+1}=\prod p_i^{l_{m+1,i}}$ is constructed in such a way that all $l_{m+1,i}$ where $i>m$ is divisible by 3. This is necessary for $\varphi$ to possibly be cube because no other terms before and including $p_m$ can contain any prime factor greater than $p_m$.

To proceed, we write $\varphi_m$ as
\[
\varphi_m = \prod_{i=1}^{m-1} p_1^{l'_i} \cdot (p_m-1) p_m^{2k_m-1} \cdot
p_m^{l'_m} \cdot \prod_{i=m+1}^{M} p_i^{l'_i}
\]
where $l'_i$ is abbreviation for $l_{m+1,i}$. In order to make the factor containing $p_m$ a cube, we must have $3 | l'_m + 2 k_m - 1$.

Now consider the term $(p_m-1)$. This cannot be a cube because otherwise $p_m$ would not be prime. Write the prime factorization of $(p_m-1)$ as
\[
p_m-1 = \prod_{i=1}^{m-1} p_i^{r_i}
\]
The we can write $\varphi_m$ as
\[
\varphi_m = \left( \prod_{i=1}^{m-1} p_i^{l'_i + r_i} \right) p_m^{l'_m + 2k_m-1} \left( \prod_{i=m+1}^{M} p_i^{l'_i} \right)
\]
Now consider each non-cube term $p_i^{l'_i + r_i} = p_i^{3u+s}$, where $u \ge 0$ and $s=1$ or 2. Since $\varphi$ already contains the prime factor $p_i^s$, it must also contain $p_i^{3-s}$, coming from either $p_i^{2k_i-1}$ or some other $(p_j-1)$ where $i<j<m$. In either case, $n \ge p_i^{3-s} n'$ where $n' = p_m^{k_m} \cdots p_M^{k_M}$. Written formally,
\[
\prod_{i=1}^{m-1} p_i^{3-s_i} \,\Big|\, \prod_{i=1}^{m-1} (p_i-1)p_i^{2k_i-1}
\]
where $s_i = (l'_i+r_i-1) \text{ mod } 3+1$. This provides a useful lower bound of $n$.\footnote{
Note that the lower bound \emph{cannot} be extended directly to
\[
n \ge \left( \prod_{i=1}^{m-1} p_i^{3-s_i} \right) n'
\]
}


\answer
5943040885644

\complexity

Empirical number of calls is approximately $\mathcal{O}(0.373 \times n^{0.593})$. Don't know what's the exact complexity.

%Time complexity: $\mathcal{O}(1.35 \times n^{1.15})$

%Space complexity: $\mathcal{O}(1.44 \times n^{0.71})$

\end{document}
